updated: 2022-01-23_12:32:31-05:00

Exam Prep

Pumping Lemma: HW Problems

A = {www|w \i\n {ab}*}; prove A is not regular

suppose A is regular
w=apbapbapbw = a^{p}ba^{p}ba^{p}b, |w| ≥\ge p

  1. |xy| ≤\le p
  2. y ≠\ne e
  3. xyk^{k}z ∈\in L ∀\forall k ≥\geq 0

1: clear that xy are all a's

  • so for k = 0 => xy0^{0}z
    • xy = ap−∣y∣bapbapb∉A^{p-|y|}ba^{p}ba^{p}b\notin A
    • same for k = 2, p+y

Y = {w|w=x1#x2#x3...xk}

ERROR FAILURE
Σ\Sigma = {1, #}
for k ≥\geq 0 xi ∈\in 1⋆^{\star}, xi ≠\neq xj for i ≠\ne j

let w = 1#1p^{p}#12p^{2p}
xy is 1#1p^{p}
y can be 1#

  • 1#1#1p^{p}#12p^{2p} (fail)

y can be #

  • 1##... (fail)

y can be 1#1g^{g} where g < p

  • 1#1g^{g}
  • she's getting a bit confused here
  • assumption is x is empty
    • we can't assume that
  • forget about it
  • do w = 1^p, 1^p+1,
  • then pump up, p+y will be equal to another element from 1->p

ADD = {x = y + 2 | x,y,z are all binary}

w = 10p^{p}= 1p+1^{p}+1
k = 0; xy^0z =>

take home hw:

(from book)
2.30:
a) {0n^n 1n^n 0n^n 1n^n | n ≥\ge 0} is not a CFL
d) {t1_1 # t2_2 # ... # tk_k | k ≥\ge 2, each ti_i ∈\in {a,b}⋆^{\star} and ti_i = tj_j for some i ≠\ne j}
2.33:
show that f = {ai^{i} bj^{j} | i = kj for some positive integer k} is not a CFL

let's do 2.33:

show that f = {ai^{i} bj^{j} | i = kj for some positive integer k} is not a CFL

let w = a2p2b2pa^{2p^{2}}b^{2p} (k = p) the nested square is not the same square as on a
a = 2p * p

uvxyzuvxyz

  1. |vxy|≤\lep
  2. vy ≠\ne 0
  3. uvkxyz∈L∀k≥0uv^{k}xy^{z}\in L \forall k \ge 0

v or y contain more than one kind of symbol

let k = 2
uv2xy2∉Luv^{2}xy^{2}\notin L
when we repeat them, out of order:

both v & y contain a's

let k = 2
uv2xy2∉Luv^{2}xy^{2}\notin L

| v y | = l
l < p < 2p
a2p2+lb2pa^{2p^{2}+l}b^{2p}

2p^2+l is not a multiple of 2p

both v & y contain only b's

uvmxymzuv^{m}xy^{m}z

m = 2p^2

a2p2b2p+2p2a^{2p^{2}}b^{2p+2p^{2}} i < j ≠\ne L

V contains only a's and y contains only b's

uvmxymzuv^{m}xy^{m}z

ag+∣v∣bh+∣y∣a^{g+|v|}b^{h+|y|}
Pasted image 20211105095854

Cover 3 conditions, same x, same y, 2 kinds of symbols